package main;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LargestValues {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode left1 = new TreeNode(4);
        TreeNode right1 = new TreeNode(2);
        root.left = left1;
        root.right = right1;
        left1.left = new TreeNode(5);
        left1.right = new TreeNode(1);
        right1.right = new TreeNode(9);
        System.out.println(new LargestValues().largestValues(root));
    }
    public List<Integer> largestValues(TreeNode root){
        int current = 0;
        int next = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null){
            queue.offer(root);
            current = 1;
        }
        List<Integer> result = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            current--;
            max = Math.max(max,node.val);
            if (node.left != null){
                queue.offer(node.left);
                next++;
            }
            if (node.right != null){
                queue.offer(node.right);
                next++;
            }
            if (current == 0){
                result.add(max);
                max = Integer.MIN_VALUE;
                current = next;
                next = 0;
            }
        }
        return result;
    }
    public List<Integer> largestValues2(TreeNode root){
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        if (root != null){
            queue1.offer(root);
        }
        List<Integer> result = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        while (!queue1.isEmpty()){
            TreeNode node = queue1.poll();
            max = Math.max(max,node.val);
            if (node.left != null){
                queue2.offer(node.left);
            }
            if (node.right != null){
                queue2.offer(node.right);
            }
            if (queue1.isEmpty()){
                result.add(max);
                max = Integer.MIN_VALUE;
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return result;
    }
}
